UVa/562 - Dividing coins/562.cpp

   1 /*
   2 /*
   3   Solution to problem: 562 - Dividing coins
   4   (From the UVa Online Judge
   5   http://icpcres.ecs.baylor.edu/onlinejudge/
   6   )
   7
   8   Author: Andres Mejia-Posada
   9   http://blogaritmo.factorcomun.org
  10
  11   Accepted.
  12  */
  13 #include <stdio.h>
  14 #include <stdlib.h>
  15
  16 int main(){
  17   int n, s, c;
  18   scanf("%d", &n);
  19   while (n--){
  20     scanf("%d", &c);
  21     int m[c];
  22     s = 0;
  23     for (int i=0; i<c; ++i){
  24       scanf("%d", &m[i]);
  25       s += m[i];
  26     }
  27
  28     bool dp[c][s+1];
  29     for (int d=0; d<=s; ++d)
  30       dp[0][d] = false;
  31
  32     if (c == 0)
  33       printf("0\n");
  34     else {
  35       dp[0][m[0]] = true;
  36       for (int i=1; i<c; ++i)
  37         for (int d=0; d<=s; ++d){
  38           dp[i][d] = dp[i-1][abs(d - m[i])];
  39           if (d + m[i] <= s)
  40             dp[i][d] |= dp[i-1][d + m[i]];
  41         }
  42
  43       for (int d=0; d<=s; ++d)
  44         if (dp[c-1][d]){
  45           printf("%d\n", d);
  46           break;
  47         }
  48     }
  49   }
  50   return 0;
  51 }